#coding=utf-8 
'''
Created on 2012-9-29

@author: infear
'''
#http://blog.csdn.net/v_JULY_v/article/details/6234496

import re
import node
import random
import LinkedNode;

#1有一个整数数组，请求出两两之差绝对值最小的值,
#这个题暂时还没有找到比较好的方法

#2、写一个函数，检查字符是否是整数，如果是，返回其整数值。（或者：怎样只用4行代码编写出一个从字符串到长整形的函数？）
def ConvertToLong():
    _str=raw_input("Enter Long Int:")
    regression='([0-9])+$'
    if re.match(regression,_str):
        return long(_str)
    return "Format Wrong"

#3、给出一个函数来输出一个字符串的所有排列
def AllOrderString(_str):
    if len(_str)==1:
        yield (_str,)
    else:
        _set=set()
        for i in range(len(_str)):
            if _str[i] not in _set:
                _set.add(_str[i])
                for result in AllOrderString(_str[:i]+_str[i+1:]):
                    yield (_str[i],)+result
        
#4、（a）请编写实现malloc()内存分配函数功能一样的代码。 
#（b）给出一个函数来复制两个字符串A和B。字符串A的后几个字节和字符串B的前几个字节重叠。
def mergeTwoStr(_str_a,_str_b):
    _len_a,_len_b=len(_str_a),len(_str_b)
    i,j=_len_a,_len_b
    while _str_b[:j]!=_str_a[i-j:]:
        j=j-1
    return _str_a+_str_b[j:]

#5、怎样编写一个程序，把一个有序整数数组放到二叉树中？
def constructBTreeFromSortedArray(arr):
    if arr==None or len(arr)==0:
        return None
    else:
        _mid=len(arr)/2
        root=node.node(None,None,arr[_mid])
        left=constructBTreeFromSortedArray(arr[:_mid])
        right=constructBTreeFromSortedArray(arr[_mid+1:])
        root._left=left
        root._right=right
        return root

#6、怎样从顶部开始逐层打印二叉树结点数据？请编程
def level_order(nod):
    print "level order"
    _list1=[]
    _list2=[]
    _list1.append(nod)
    while(len(_list1)!=0 or len(_list2)!=0):
        while(len(_list1)!=0):
            temp=_list1.pop()
            temp._print()
            if temp._left is not None:
                _list2.append(temp._left)
            if temp._right is not None:
                _list2.append(temp._right)
        while(len(_list2)!=0):
            temp=_list2[len(_list2)-1]
            _list2.pop()
            _list1.append(temp);

#7、怎样把一个链表掉个顺序（也就是反序，注意链表的边界条件并考虑空链表）？
def reverseUsingRecrusive(nod):
    if nod is not None and nod.next is not None:
        head=reverseUsingRecrusive(nod.next)
        nod.next.next=nod
        nod.next=None
        return head
    else:
        return nod
#7、怎样把一个链表掉个顺序（也就是反序，注意链表的边界条件并考虑空链表）？       
def reverse(nod):
    _p1=None
    _p2=nod
    while(_p2 is not None):
        _p3=_p2.next
        _p2.next=_p1
        _p1=_p2
        _p2=_p3
    return _p1

#9编程实现两个正整数的除法
def divide(x,y):
    if isinstance(x, int) and x>0:
        if isinstance(y,int) and y>0:
            count=0;
            while(x>=y):
                x=x-y
                count=count+1
            remainder=x
            return count,remainder
    return -1,-1

#10、在排序数组中，找出给定数字的出现次数
#比如 [1, 2, 2, 2, 3] 中2的出现次数是3次。
def findSortedNumber(arr,num):
    if arr is None or len(arr)==0:
        return 0
    else:
        mid=len(arr)/2
        if arr[mid]>num:
            return findSortedNumber(arr[:mid],num)
        elif arr[mid]<num:
            return findSortedNumber(arr[mid+1:],num)
        else:
            return 1+findSortedNumber(arr[:mid],num)+findSortedNumber(arr[mid+1:],num)

#11、平面上N个点，每两个点都确定一条直线，
#求出斜率最大的那条直线所通过的两个点（斜率不存在的情况不考虑）。时间效率越高越好。
#解答：先用堆排序把这些点按照x的坐标排序，时间为nlog(n),然后 发现 相邻的三个点ABC,AC的斜率一定在AB和BC，以此类推，AD的斜率一定在AB,BC,CD之间，所以只需求相邻两个点的
#斜率的最大值，即AB,BC,CD,DE...的最大值即可，这里只是吧堆排实现了一下 
def siftup(_arr,i):
    if i==1:
        pass
    else:
        while i!=1:
            if _arr[i]>_arr[i/2]:
                _arr[i],_arr[i/2]=_arr[i/2],_arr[i]
                i=i/2
            else:
                break;

def siftdown(_arr,i,n):
    if i>n/2:
        pass
    else:
        while i<=n/2:
            i=2*i
            if i+1<=n and _arr[i+1]>_arr[i]:
                i=i+1
            if _arr[i/2]<_arr[i]:
                _arr[i/2],_arr[i]=_arr[i],_arr[i/2]
            else:
                break

def insert(_arr,x,n):
    _arr.append(x)
    siftup(_arr,n+1)

def delete(_arr,i,n):
    if i==n:
        _arr.remove(i)
    else:
        x,_arr[i]=_arr[i],_arr[n]
        if _arr[n]>x:
            siftup(_arr,i)
        else:
            siftdown(_arr,i)   

def MakeHeap(_arr,n):
    i=n/2
    while i!=0:
        siftdown(_arr,i,n)
        i=i-1
        
    
            
                    

#12、一个整数数列，元素取值可能是0~65535中的任意一个数，相同数值不会重复出现。0是例外，可以反复出现。
#请设计一个算法，当你从该数列中随意选取5个数值，判断这5个数值是否连续相邻。
#注意：
#- 5个数值允许是乱序的。比如： 8 7 5 0 6
#- 0可以通配任意数值。比如：8 7 5 0 6 中的0可以通配成9或者4
#- 0可以多次出现。
#- 复杂度如果是O(n2)则不得分。
#其实只需要判断最大的和最想的差是不是在0到4之间就可以了 ，这里的 最大和最小值比较忽略0值 
def func(_arr):
    _len=len(_arr)
    index=random.sample(range(0,_len),5)
    _list=[]
    _min,_max=65536,-1
    for i in index:
        _list.append(_arr[i])
        if _arr[i]<_min and _arr[i]!=0:
            _min=_arr[i]
        if _arr[i]>_max and _arr[i]!=0:
            _max=_arr[i]
    if _max-_min<=4:
        return _list,True
    else:
        return _list,False

#13、设计一个算法，找出二叉树上任意两个结点的最近共同父结点。
#复杂度如果是O(n2)则不得分。
#verify whether 'parent' is the parent of the child 
def isChild(parent,child):
    if(child is None):
        return True
    elif(parent is None):
        return False
    elif(parent==child):
        return True
    else:
        return isChild(parent._left, child) or isChild(parent._right, child) 

#find common parent of 'nod1' and 'nod2' in tree 'root'
def findNearestCommonParent(root,nod1,nod2):
    if not isChild(root, nod1) or not isChild(root, nod2):
        return None
    else:
        if isChild(root._left, nod1) and isChild(root._left, nod2):
            return findNearestCommonParent(root._left, nod1, nod2)
        elif isChild(root._right,nod1) and isChild(root._right, nod2):
            return findNearestCommonParent(root._right, nod1, nod2)
        else:
            return root
        
#14、一棵排序二叉树，令 f=(最大值+最小值)/2，
#设计一个算法，找出距离f值最近、大于f值的结点。
#复杂度如果是O(n2)则不得分。
def findClose(N,root):
    if root is None or root.value==N:
        return root
    if root.value>N:
        left_find=findClose(N,root._left)
        if left_find is None:
            return root
        return left_find
    else:
        return findClose(N,root._right)


#15、一个整数数列，元素取值可能是1~N（N是一个较大的正整数）中的任意一个数，相同数值不会重复出现。
#设计一个算法，找出数列中符合条件的数对的个数，满足数对中两数的和等于N+1。
#复杂度最好是O(n)，如果是O(n2)则不得分。
def findpair(_arr,N):
    _list=[0]*(N+1)
    for i in _arr:
        _list[i]=1
    for i in range(0,N/2):
        if _list[i]==1 and _list[N+1-i]==1:
            yield i,N+1-i

#补充；合并两个排序的链表
def mergeList(h1,h2):
    head=LinkedNode.LinkedNode(None,-1)
    p1,p2,p3=h1,h2,head
    while p1 is not None and p2 is not None:
        while p2 is not None and p1.value>p2.value:     
            p3=p2
            p2=p2.next
        p4=p1.next
        p3.next=p1
        p1.next=p2
        p3=p1
        p1=p4
    if p2 is None:
        if p1 is not None:
            p3.next=p1
    else:
        if p1 is None:
            p1.next=p2
    return head.next
            
    
#test 2
#while True:
#    print ConvertToLong()

#test 3
#result=list(AllOrderString(_str='abcdd'));
#print result

#test 4b
#print mergeTwoStr("strabc","abcd")

#test5
#root=constructBTreeFromSortedArray([2,5,7,10,11,12])
#node.mid_order(root)

#14
#try:
#    findClose(3,root)._print()
#except:
#    print "Not Find"

#test9
#print divide(10,3),divide(100,10),divide(-1,0)

#test10
#print findSortedNumber([1,2,2,2,3],2)

#test 11
#_arr=[-1,4,6,8,3,1,9]
#MakeHeap(_arr,6)
#print _arr
#end=6
#while end!=1:
#    _arr[1],_arr[end]=_arr[end],_arr[1]
#    end=end-1
#    siftdown(_arr,1,end)
#
#print _arr

#test 12
#_list=[]
#for i in range(0,1000):
#    _list.append(random.randrange(start=0,stop=65536))
#for i in range(0,50):
#    print func([1,2,3,4,7,9,12,0,0,0,0,0,0])

#test15
#print list(findpair([1,3,5,7,8,9],10))

#test mergeList
n1=LinkedNode.LinkedNode(None,7)
n2=LinkedNode.LinkedNode(n1,5)
n3=LinkedNode.LinkedNode(n2,2)

n4=LinkedNode.LinkedNode(None,6)
n5=LinkedNode.LinkedNode(n4,4)
n6=LinkedNode.LinkedNode(n5,3)

head=mergeList(n3,n6)
while head is not None:
    print head.value
    head=head.next
